package com.xiyou.week06.dp;

/**
 * 152. 乘积最大子数组
 *
 * @ClassName：MaxProduct
 * @Author：西柚
 * @Date：2022/2/25 5:48 下午
 * @Versiion：1.0
 */
public class MaxProduct {

    /**
     * 输入: nums = [2,3,-2,4]
     * 输出: 6
     * 解释: 子数组 [2,3] 有最大乘积 6。
     *
     * @param nums
     * @return
     */
    public int maxProduct(int[] nums) {
        int n = nums.length;
        int fmax[] = new int[n];
        int fmin[] = new int[n];
        fmax[0] = nums[0];
        fmin[0] = nums[0];
        for (int i = 1; i < n; i++) {
            fmax[i] = Math.max(Math.max(fmax[i - 1] * nums[i], fmin[i - 1] * nums[i]), nums[i]);
            fmin[i] = Math.min(Math.min(fmax[i - 1] * nums[i], fmin[i - 1] * nums[i]), nums[i]);
        }
        int ans = fmax[0];
        for (int i = 1; i < n; i++) {
            ans = Math.max(ans, fmax[i]);
        }
        return ans;
    }

    public static void main(String[] args) {
        int[] nums = {-2, 3, -4};
        MaxProduct maxProduct = new MaxProduct();
        System.out.println(maxProduct.maxProduct(nums));
    }
}
